A threshold-2 (or second threshold) function (i.e., T2) has practical usage, particularly in content addressable memory (CAM) applications where the second threshold function can be used as part of a multiple match detector. A value generated by a second threshold function indicates whether more than one argument of the function is non-zero. The second threshold function is expressed by equation 1, shown in FIG. 1, where each of X1 through XN is a binary (i.e., 0 or 1) input argument. In terms of logical AND operations and logical OR operations, the second threshold function in equation 1 is expressed by equation 2, shown in FIG. 1. A standard method of implementation for T2 is based on expansions shown in equations 3 through 5, also shown in FIG. 1. The standard method consists of a hierarchical set of units simultaneously implementing both functions T1 and T2.
Referring to FIG. 2, a block diagram of a conventional 2-input unit 10 is shown. The Z2 unit (or circuit) 10 consists of just two logic gates, a logical OR gate 12 and a logical AND gate 14. Input signals X1 and X2 are applied to each of the logic gates 12 and 14. Output signals T1 and T2 are generated by the logic gates 12 and 14, respectively.
Referring to FIG. 3, a block diagram of a conventional N-input unit 20 is shown. Equations 3 and 4 suggest that a ZN unit (or circuit) 20 can be implemented using (i) two logical units 22 and 24 and (ii) four logic gates 26, 28, 30 and 32. The logic unit 22 (i.e., ZL unit) implements both the T1 and the T2 functions for L input signals X1 through XL (i.e., values X1 through XL). The logic unit 24 (i.e., ZN−L unit) implements both the T1 and the T2 functions for the N−L input signals X(L+1) through XN (i.e., values XL+1 through XN).
Starting with the Z2 unit and recursively applying the decomposition shown just above can be used to construct ZN units, for N=4, 8 and 16 inputs, using respectively 2×2+4=8, 2×8+4=20 and 2×20+4=44 logic gates. Generally, 3N−4 logic gates are used in a conventional design, where N is the number of inputs. A delay, measured as maximum number of logic gates along paths from the input signals X1 through XN to the output signals T1 and T2 is one delay time for a Z2 unit, three delay times for a Z4 unit, five delay times for a Z8 unit and seven delay times for a Z16 unit. Generally, the delay for the conventional method may be expressed by equation 6, shown in FIG. 1.
Referring to FIG. 4, a block diagram of a conventional 16-input unit 50 is shown. The Z16 unit 50 consists of multiple logical OR gates and multiple logical AND gates. The numbers at the inputs and/or outputs to each of the logical gates represent delays from the input signals X1 through X16, assuming that all of the input signals X1 through X16 arrive and/or change simultaneously and no wire delay is taken into consideration. A longest input-to-output path in the Z16 unit 50 goes from the input signal X16 to the output signal T2 and has a delay equal to seven. Many of the logic gates have non-synchronous inputs, that is, inputs with (essentially) different signal arrive times.